package sword.chapter10Trie;

import java.util.Arrays;
import java.util.List;

/**
 * 替换单词
 *
 * 前缀树
 * 1. 构建前缀树
 * 2. 查询前缀树
 *
 * @author K
 * @date 2021/12/21 09:07
 */
public class S63ReplaceWords {

    public static String s63(List<String> words, String sentence) {
        TrieNode root = build(words);
        String[] strs = sentence.split(" ");
        for (int i = 0; i < strs.length; i++) {
            String prefix = findPrefix(root, strs[i]);
            if (!prefix.isEmpty()) {
                strs[i] = prefix;
            }
        }

        return String.join(" ", strs);
    }

    public static TrieNode build(List<String> words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                if (node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }
                node = node.children[ch - 'a'];
            }
            node.isWord = true;
        }

        return root;
    }

    public static String findPrefix(TrieNode root, String word) {
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        for (char ch : word.toCharArray()) {
            if (node.isWord || node.children[ch - 'a'] == null) {
                break;
            }
            sb.append(ch);
            node = node.children[ch - 'a'];
        }

        return node.isWord ? sb.toString() : "";
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("cat", "bat", "rat");
        String sentence = "the cattle was rattled by the battery";
        String result = s63(words, sentence);
        System.out.println();
    }
}
